#ifndef __Polygon_h_GUARD_
#define __Polygon_h_GUARD_

#include <vector>
#include <list>
#include <map>
#include "RTree.h"
// #define _TEST	// 调试输出
// #define _SORT_ENABLE_	// 是否开启查询结果 id 按从小到大排序
// #define _TEST_PERF	// 是否使用 gperftools 进行性能分析

#ifdef _SORT_ENABLE_
#include <algorithm>
#endif

const int MAXNODES = 16;	// RTree 节点中最大子节点数
// const int MAXTREES = 1;		// 存储 Polygon 数据的 RTree 数目
extern std::vector<int> ans;
extern bool sum;
extern int count;

struct Polygon;

struct Node		// 节点定义
{
	Node(): x(0.0), y(0.0), id(0) { }
	Node(int id, double x, double y): id(id), x(x), y(y) { }
	double x, y;	// 横纵座标
	int id;

	static std::map<int, Node*> m;	// 保存 id 对应的节点的指针
	static double min[2], max[2];	// 将点转换成“矩形”所需的数组
	// static int flag;
	static void setRec(double &px, double &py)	// 点座标转换为矩形座标
	{ min[0] = max[0] = px, min[1] = max[1] = py; }
};

typedef RTree<std::pair<double *, bool> *, double, 2, double, MAXNODES> EdgeType;

struct Polygon
{
	Polygon(): id(0) { }
	Polygon(int id, std::vector< std::pair<double, double> > &pt);
	double min[2], max[2];	// 多边形所在矩形
	int id; // , tpos;	// tpos 记录所在 R-Tree 下标
	EdgeType edge;		// 使用 R-树储存多边形的各个顶点
	static std::map<int, Polygon*> m;		// 保存 id 对应的多边形指针
	// static int flag;
};

// 判断线段 p1 p2 与 y 处从 x 开始沿 x 轴正方向的射线是否有交点
bool judgePos(double px, double py, std::pair<double, double> &p1, std::pair<double, double> &p2);

bool pointInPolygon(double x, double y, Polygon &pol);

bool pointSearchCallback(Node *ndptr, void *arg);

bool polygonSearchCallback(Polygon *polptr, void *arg);

// 在 R-树 中搜索可能在射线上的边
bool edgeSearchCallback(std::pair<double *, bool> *dt, void *arg);

extern RTree<Node*, double, 2, double, MAXNODES> pointTree;
extern RTree<Polygon*, double, 2, double, MAXNODES> polygonTree; // [MAXTREES];

void AddPolygon(int id, int n, std::vector< std::pair<double, double> > &polygon);
void DeletePolygon(int id);
std::vector<int> QueryPolygon(int n, std::vector< std::pair<double, double> > &polygon);
void AddPoint(int id, double x, double y);
void DeletePoint(int id);
std::vector<int> QueryPoint(double x, double y);
#endif
